package 面试经典150题.矩阵;

//用 O(m+n)额外空间
//
// 两遍扫matrix,第一遍用集合记录哪些行,哪些列有0;第二遍置0

import java.util.HashSet;
import java.util.Set;

public class T73矩阵置零 {

    public void setZeroes(int[][] matrix) {
        Set<Integer> rowSet = new HashSet<>();
        Set<Integer> colSet = new HashSet<>();
        int m = matrix.length;
        int n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    //把行列加入两个set里面
                    rowSet.add(i);
                    colSet.add(j);
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //如果集合里面包含下标，那么就把对应的元素置零
                if (rowSet.contains(i) || colSet.contains(j)) {
                    matrix[i][j] = 0;
                }
            }
        }

    }
}
